0530. 二叉搜索树的最小绝对差【简单】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 中序遍历计算相邻成员之间的差值
• 3. 🔗 引用

1. 📝 题目描述

• leetcode

注意

• 相同例题：783. 二叉搜索树节点最小距离

---

• 给你一个二叉搜索树的根节点 root，返回 树中任意两不同节点值之间的最小差值。
• 差值是一个正数，其数值等于两值之差的绝对值。

---

示例 1：

输入：root = [4,2,6,1,3]
输出：1

示例 2：

输入：root = [1,0,48,null,null,12,49]
输出：1

---

提示：

• 树中节点的数目范围是 [2, 10^4]
• 0 <= Node.val <= 10^5

2. 🎯 s.1 - 中序遍历计算相邻成员之间的差值

1.js

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var getMinimumDifference = function (root) {
  let minDiff = Infinity
  let prev = null

  // 中序遍历函数
  function inorder(node) {
    if (!node) return

    // 遍历左子树
    inorder(node.left)

    // 处理当前节点
    if (prev !== null) {
      minDiff = Math.min(minDiff, node.val - prev)
    }
    prev = node.val

    // 遍历右子树
    inorder(node.right)
  }

  inorder(root)
  return minDiff
}

2.js

/**
 * @param {TreeNode} root
 * @return {number}
 */
var minDiffInBST = function (root) {
  let minDiff = Infinity
  let prev = null
  const stack = []
  let current = root

  // 迭代中序遍历
  while (current || stack.length > 0) {
    // 一直向左走到底
    while (current) {
      stack.push(current)
      current = current.left
    }

    // 处理栈顶节点
    current = stack.pop()

    if (prev !== null) {
      minDiff = Math.min(minDiff, current.val - prev)
    }
    prev = current.val

    // 转向右子树
    current = current.right
  }

  return minDiff
}

• 时间复杂度：$O(n)$，其中 $n$ 是二叉搜索树的节点数，需要遍历每个节点一次
• 空间复杂度：$O(h)$，其中 $h$ 是二叉搜索树的高度，递归调用栈的深度。平均情况下为 $O(\log n)$，最坏情况下为 $O(n)$
• 1.js 递归遍历，2.js 迭代遍历；
• 算法思路：
  1. 中序遍历：
     • 利用 BST 的性质，中序遍历得到有序序列
     • 在遍历过程中直接 计算相邻元素的差值
  2. 差值计算：
     • 使用 prev 记录前一个访问节点的值
     • 当前节点值与前一个节点值的差就是可能的最小差值之一
     • 因为序列有序，所以相邻元素的差值最小
  3. 维护最小差值：
     • 使用 minDiff 记录当前找到的最小差值
     • 每次计算新差值时更新 minDiff

3. 🔗 引用

• 783. 二叉搜索树节点最小距离